DROPS

Document

DOI: 10.4230/LIPIcs.STACS.2020.6

An Automaton Group with PSPACE-Complete Word Problem

Authors: Jan Philipp Wächter and Armin Weiß

Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)

Abstract

We construct an automaton group with a PSPACE-complete word problem, proving a conjecture due to Steinberg. Additionally, the constructed group has a provably more difficult, namely EXPSPACE-complete, compressed word problem. Our construction directly simulates the computation of a Turing machine in an automaton group and, therefore, seems to be quite versatile. It combines two ideas: the first one is a construction used by D'Angeli, Rodaro and the first author to obtain an inverse automaton semigroup with a PSPACE-complete word problem and the second one is to utilize a construction used by Barrington to simulate circuits of bounded degree and logarithmic depth in the group of even permutations over five elements.

Cite as

Jan Philipp Wächter and Armin Weiß. An Automaton Group with PSPACE-Complete Word Problem. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 6:1-6:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{wachter_et_al:LIPIcs.STACS.2020.6,
  author =	{W\"{a}chter, Jan Philipp and Wei{\ss}, Armin},
  title =	{{An Automaton Group with PSPACE-Complete Word Problem}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{6:1--6:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Paul, Christophe and Bl\"{a}ser, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.6},
  URN =		{urn:nbn:de:0030-drops-118674},
  doi =		{10.4230/LIPIcs.STACS.2020.6},
  annote =	{Keywords: automaton group, word problem, PSPACE, compressed word problem}
}

Search Results

Documents authored by Wächter, Jan Philipp

An Automaton Group with PSPACE-Complete Word Problem

Abstract

Cite as

Thanks for your feedback!

Could not send message